Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
Example 2:
Input: n = 1, k = 1 Output: [[1]]
Constraints:
1 <= n <= 201 <= k <= n
Average Rating: 3.63 (40 votes)
Solution
Approach 1: Backtracking
Algorithm
Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.
Here is a backtrack function
which takes a first integer to add and
a current combination as arguments backtrack(first, curr).
-
If the current combination is done - add it to output.
-
Iterate over the integers from
firstton.-
Add integer
iinto the current combinationcurr. -
Proceed to add more integers into the combination :
backtrack(i + 1, curr). -
Backtrack by removing
ifromcurr.
-
Implementation
Complexity Analysis
-
Time complexity : O(kCNk), where CNk=(N−k)!k!N! is a number of combinations to build.
append / pop(add / removeLast) operations are constant-time ones and the only consuming part here is to append the built combination of lengthkto the output. -
Space complexity : O(CNk) to keep all the combinations for an output.
Approach 2: Lexicographic (binary sorted) combinations
Intuition
The idea here is not just to get the combinations but to generate them in a lexicographic sorted order.
Algorithm
The algorithm is quite straightforward :
-
Initiate
numsas a list of integers from1tok. Addn + 1as a last element, it will serve as a sentinel. Set the pointer in the beginning of the listj = 0. -
While
j < k:-
Add the first k elements from
numsinto the output, i.e. all elements but the sentinel. -
Find the first number in nums such that
nums[j] + 1 != nums[j + 1]and increase it by onenums[j]++to move to the next combination.
-
Implementation
Complexity Analysis
-
Time complexity : O(kCNk), where CNk=(N−k)!k!N! is a number of combinations to build.
The external while loop is executed CNk times since the number of combinations is CNk. The inner while loop is performed CN−jk−j times for a given
j. In average over CNk visits from the external loop that results in less than one execution per visit.
Hence the most consuming part here is to append each combination of length k (CNk combinations in total) to the output, that takes O(kCNk) time.You could notice that the second algorithm is much faster than the first one despite they both have the same time complexity. It's a consequence of dealing with the recursive call stack frame for the first algorithm, and the effect is much more pronounced in Python than in Java.
-
Space complexity : O(CNk) to keep all the combinations for an output.
Links
July 2, 2019 5:50 PM
Shouldn't the backtracking approach's space complexity be the same as the time complexity of O(k * nCk)? We have nCk subsets and they're all k in size
Last Edit: March 29, 2019 9:01 PM
solution 1 should return after appending a complete combination. otherwise the combination will grow beyond size K
July 27, 2019 11:20 AM
Add return condition for approach1 (prune unused call stack).
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(first, curr):
# if the combination is done
if len(curr) == k:
output.append(curr[:])
return
if (k - len(curr)) > (n - first + 1):
return
for i in range(first, n + 1):
# add i into the current combination
curr.append(i)
# use next integers to complete the combination
backtrack(i + 1, curr)
# backtrack
curr.pop()
output = []
curr = []
backtrack(1, curr)
return output
March 11, 2021 1:40 PM
Approach 2 is not clear at all.
The time complexity of O(KCn,k) is definitely wrong. For example, let K==N, then we have the time complexity to be O(N). However, in the first approach, it enumerates all 2^N combinations.
In Approach 1, why output.append(curr[:]), not output.append(curr)? I know lists are referred by references, but cannot distinguish the use case in problems like this.
July 18, 2019 11:25 PM
The space complexity of backtracking should be O(k+Ckn)
"The idea here is not just to get the combinations but to generate them in a lexicographic sorted order." - not sure why the author says generations like [1,2] [1,3] [2,3] [1,4]...(as in the picture below) is a lexicographic sorted order.
why do we need to create a shallow copy of curr in the python solution? (curr[:])
November 11, 2020 10:44 AM
Re approach #2, why are we setting nums[j] = j + 1 not to nums[j+1]?
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: vector<vector<int>> combine(int n, int k) { }};